/*
* leetcode练习题
*
*/


/*49 字母异位词分组*/
#if 0
/*
*思路：将单词重新排序，排序后相同的单词就是异位词
*/
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> hash;
    for (auto str : strs) 
    {
        string s = str;
        sort(s.begin(), s.end());//对字符串排序，作为哈希表的键值
        hash[s].push_back(str);
    }
    vector<vector<string>> ans;
    for (auto h : hash) 
    {
        ans.push_back(h.second);
    }
    return ans;
}

int main()
{
    string input;
    while (cin >> input)
    {
        istringstream is(input);
        vector<string> table;
        string add;
        while (getline(is, add, ' '))
        {
            table.push_back(add);
        }

        vector<vector<string>> t = groupAnagrams(table);

        for (int i = 0; i < t.size(); ++i)
        {
            for (int j = 0; j < t[i].size(); ++j)
            {
                cout << t[i][j] << " ";
            }
            cout << endl;
        }
    }
}

#endif

/*383 赎金信*/
#if 0
/*
*给定两个字符串，判断能不能用一个字符串表示另一个
*/
/*
*思路：计算两个字符串中字母出现的次数，然后比较这些次数
*/
bool canConstruct(string ransomNote, string magazine)
{
    int times1[26];
    int times2[26];
    for (int i = 0; i < 26; i++)
    {
        times1[i] = 0;
        times2[i] = 0;
    }
    for (int i = 0; i < ransomNote.size(); i++)
    {
        times1[ransomNote[i] - 'a']++;
    }
    for (int i = 0; i < magazine.size(); i++)
    {
        times2[magazine[i] - 'a']++;
    }
    for (int i = 0; i < 26; i++)
    {
        if (times2[i] < times1[i])
            return false;
    }
    return true;
}


int main()
{
    string ransomNote, magazine;
    cin >> ransomNote;
    cin >> magazine;

    cout << canConstruct(ransomNote, magazine) << endl;
}

#endif


/*344 反转字符串*/
#if 0
/*
*将字符串反过来，不要另外分配空间
*/
/*
*思路：双指针，交换指针指向的数据
*/

int main()
{
    string str;
    cin >> str;

    char temp; 
    int n = str.length() - 1;
    for (int i = 0; i < n - i; i++) {
        temp = str[i];
        str[i] = str[n - i];
        str[n - i] = temp;
    }

    cout << str << endl;
}

#endif

/*387 字符串中的第一个唯一字符*/
#if 0
/*
*给定字符串，找到第一个不重复的字符,返回索引
*/
/*
*思路：两次遍历，第一次遍历出现的次数，第二次找到第一个出现次数为1的
*/
int firstUniqChar(string s) 
{
    map<char, int> a;
    for (int i = 0; i < s.size(); i++) {
        ++a[s[i]];
    }
    for (int i = 0; i < s.size(); i++) {
        if (a[s[i]] == 1)return i;
    }
    return -1;
}

int main()
{
    
    string str;
    cin >> str;
    cout << firstUniqChar(str) << endl;
}

#endif


/*6 Z字形变换*/
#if 0
/*
*给定字符串，根据行数，按照从下往上从左往右排列
*/
string convert(string s, int numRows) 
{
    if (numRows == 1)
        return s;
    int cycle = numRows * 2 - 2;
    string res;

    int l = s.length();
    for (int k = 0; k < numRows; k++) 
    {
        if (k == 0 || k == numRows - 1) {
            for (int i = k; i < l; i += cycle) 
	    {
                res.push_back(s[i]);
            }
        }
        else
       	{
            for (int i = k, j = cycle - k; i < l; i += cycle, j += cycle) 
	    {
                res.push_back(s[i]);
                if (j < l) res.push_back(s[j]);
            }
        }
    }
    return res;
}

int main()
{

    string str;
    int row;
    cin >> str;
    cin >> row;

    cout << convert(str, row) << endl;

}

#endif

/*387 简化路径*/
#if 0
/*
*给定字符串，指向unix风格的绝对路径，将其转换成简介路径
*/
string simplifyPath(string path)
{
    stringstream ss;
    ss << path;
    string readcache;
    vector<string> filename;
    while (getline(ss, readcache, '/')) 
    {
        if (readcache == "") 
        {
            continue;
        }
        else if (readcache == ".") 
        {
            continue;
        }
        else if (readcache == "..") 
        {
            if (filename.size() > 0)
                filename.pop_back();
        }
        else 
        {
            filename.push_back(readcache);
        }
    }

    string ans = "";

    for (int i = 0; i < filename.size(); i++) 
    {
        ans.append("/" + filename[i]);
    }
    if (ans == "") 
    {
        return "/";
    }
    return ans;
}


int main()
{
    string str;
    cin >> str;
    cout << simplifyPath(str) << endl;
}

#endif

/*11 难度中等 盛最多水的容器*/
#if 0
/*
* 给定一个长度为n的数组height，有n条垂线，第i条线的两个端点是(i,0)和(i,height[i])
* 找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水
*/
/*
* 思路1：最简单的方法是每两个端点都计算一边，然后取最大值。时间复杂度太高
* 思路2：用两个指针，一个指向第一条线，一个指向最后一条线，计算当前的盛水量，然后移动较小的那条线，
* 然后记录当前的容量，保留容量大的那个。继续移动较小那条线，直到两条线重合。
*/
/*
* 思路2解析：盛水量是由短线和容器宽度决定的。两个指针向内移动的时候，容器宽度一定在减小，
* 此时若想让容量增加，就必须让短的那条线移动。
*/

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

int MaxArea(vector<int>& height) 
{
    vector<int>::iterator left = height.begin(), right = height.end();
    int maxVolume = 0, minHeight, width;

    right--;

    while (left <= right)
    {
        minHeight = min(*left, *right);
        width = distance(left, right);

        maxVolume = max(maxVolume, width * minHeight);

        if (*left <= *right)
        {
            left++;
        }
        else
        {
            right--;
        }
    }

    return maxVolume;
}

int main()
{
    vector<int> water;

    string input;
    string add;
    int height;
    int volume;

    cin >> input;    
    istringstream iss(input);
    stringstream st;

    while(getline(iss,add,','))
    {
        st << add;
        st >> height;
        water.push_back(height);
        st.clear();
    }

    volume = MaxArea(water);

    cout << volume << endl;
}

#endif

/*55 难度中等 跳跃游戏*/
#if 0
/*
* 给定一个非负整数数组，你最初位于数组的第一个下标
* 数组中的每个元素代表你在该位置可以跳跃 的最大长度
* 判断你是否能够达到最好一个下标
*/
/*
* 思路：遍历从当前位置到最大可到达位置，不断更新最大可到达的位置
* 如果遍历到最大可到达的位置仍然不能到达末尾，则返回false
*/

#include <iostream>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>

using namespace std;

bool canJump(vector<int>& nums) 
{
    int maxPosition = 0;

    for(int i = 0; i <= maxPosition; ++i)
    {
        maxPosition = max(maxPosition, i + nums[i]);
        if(maxPosition >= (nums.size() - 1))
        {
            return true;
        }
    }
    return false;
}

//获取一串用逗号分隔的整型数字
int main()
{
    string input;
    string add;
    int num;
    vector<int> nums;
    bool isCanJump;

    cin >> input;

    istringstream iss(input);
    stringstream ss;

    while(getline(iss,add,','))
    {
        ss << add;
        ss >> num;
        nums.push_back(num);
        ss.clear();
    }

    isCanJump = canJump(nums);

    cout << isCanJump << endl;

    return 0;
}

#endif


/* 86 难度中等 分隔链表 */
#if 0
/*
* 给你一个链表的头节点head和一个特定值x，请你对链表进行分隔，
* 使得所有小于x的节点都出现在大于或等于x的结点之前。
* 需要保留每个节点的相对位置
*/
/*
* 思路：遍历链表，让链表数值与x对比，然后用两个链表来维护对比结果
* 注意：要维护链表头
*/
#include <iostream>

using namespace std;
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* partition(ListNode* head, int x) 
{
    ListNode *left = new ListNode();
    ListNode *leftHead = left;
    ListNode *right = new ListNode();
    ListNode *rightHead = right;

    while(head != nullptr)
    {
        if(head->val < x)
        {
            left->next = head;
            left = left->next;//用于下一次迭代
        }
        else
        {
            right->next = head;
            right = right->next;
        }

        head = head->next;
    }
    right->next = nullptr;
    left->next = rightHead->next;

    return leftHead->next;
}
int main()
{

}

#endif

/*42 难度困难 接雨水*/
#if 0
/*
* 给定n个非负整数表示为宽度为1的柱子的高度，计算按此排列的柱子，下雨后能接多少水
*/
/*
* 思路：关键点在于如何找到能够盛水的区域。先找到最高的两个柱子（第一个最高的和最后一个最高的），
* 这两个柱子将区域分成三份，对这三部分单独进行处理。如果最高的柱子只有一个，则分成两部分。
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>

using namespace std;

int GetLeftMaxValueIndex(vector<int>& height,int left, int right)
{
    int maxIndex = 0;
    int maxValue = 0;
    for(int i = left; i <= right; ++i)
    {
        if(maxValue < height[i])
        {
            maxValue = height[i];
            maxIndex = i;
        }
    }
    return maxIndex;
}
int GetRightMaxValueIndex(vector<int>& height,int left, int right)
{
    int maxIndex = 0;
    int maxValue = 0;
    for(int i = left; i <= right; ++i)
    {
        if(maxValue <= height[i])
        {
            maxValue = height[i];
            maxIndex = i;
        }
    }
    return maxIndex;
}

int GetVolume(vector<int>& height, int left, int right)
{
    int volume = 0;
    int lower = min(height[left],height[right]);

    for(int i = left; i < right; ++i)
    {
        if(height[i] < lower)
        {
            volume += (lower - height[i]);
        }
    }

    return volume;
}

int trap(vector<int>& height) 
{
    int leftPillar,rightPillar,volume = 0;
    int maxIndex = height.size() - 1;
    leftPillar = GetLeftMaxValueIndex(height,0,maxIndex);
    rightPillar = GetRightMaxValueIndex(height,0,maxIndex);

    volume += GetVolume(height,leftPillar,rightPillar);

    while(leftPillar > 0)
    {
        int left = GetLeftMaxValueIndex(height,0,leftPillar - 1);
        volume += GetVolume(height,left,leftPillar);
        leftPillar  = left;
    }
    while(rightPillar < maxIndex)
    {
        int right = GetRightMaxValueIndex(height,rightPillar + 1, maxIndex);
        volume += GetVolume(height,rightPillar,right);
        rightPillar = right;
    }

    return volume;
}

//获取用逗号分隔的整型数组
int main()
{
    string tmp;
    stringstream input,toInt;
    vector<int> table;
    int add, volume;

    cin >> tmp;
    input << tmp;
    
    while(getline(input,tmp,','))
    {
        toInt << tmp;
        toInt >> add;
        table.push_back(add);
        toInt.clear();
    }

    volume = trap(table);
    cout << volume << endl;
}

#endif

/*20 难度简单 有效的括号*/
#if 0
/*
* 给定一个只包含小括号中括号大括号的字符串，判断字符串中的括号是否有效
*/
/*
* 思路：遍历字符串，将字符串入栈，碰到和栈顶匹配的字符就出队，遍历结束后栈空的话就有效
*/
#include <iostream>
#include <string>
#include <sstream>
#include <stack>

using namespace std;

bool isMatch(char left, char right)
{
    switch (left)
    {
    case '(':
    {
        if (right == ')')
        {
            return true;
        }
        else
        {
            return false;
        }
        }
    break;
    case '[':
    {
        if (right == ']')
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    break;
    case '{':
    {
        if (right == '}')
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    break;
    default:
    {
        return false;
    }
    break;
    }
}

int main()
{
    string input;
    stack<char> strQueue;
    cin >> input;

    for (int i = 0; i < input.size(); ++i)
    {

        if (!strQueue.empty() && isMatch(strQueue.top(), input[i]))
        {
            strQueue.pop();
        }
        else
        {
            strQueue.push(input[i]);
        }
    }

    if (strQueue.empty())
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

    return 0;
}

#endif


/*739 难度中等 每日温度*/
#if 0
/*
* 给定一个整数数组，表示每天温度，返回一个数组，表示在第i天之后才会有更高的温度
* 如果气温在这之后都不会升高，则用0来代替
*/
/*
* 思路：遍历每天的温度，若比栈顶的温度低或相等则将其入栈，否则栈顶出栈。
* 然后再与栈顶相比，若栈空，则入栈。
* 注意：不是将温度入栈，而是将下标入栈，否则无法找到answer的索引
*/
#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <sstream>

using namespace std;
int main()
{
    string input, add;
    stringstream ss, ass;
    vector<int> temperatures, answer;
    int temp;
    stack<int> stk;

    cin >> input;
    ss << input;
    while (getline(ss, add, ','))
    {
        ass << add;
        ass >> temp;
        temperatures.push_back(temp);
        ass.clear();
    }

    answer.resize(temperatures.size());

    for (int i = 0; i < temperatures.size(); ++i)
    {
        while (!stk.empty() && temperatures[i] > temperatures[stk.top()])
        {
            answer[stk.top()] = i - stk.top();
            stk.pop();
        }

        stk.push(i);
    }

    for (int i = 0; i < answer.size(); ++i)
    {
        cout << answer[i] << ",";
    }
    cout << endl;
}

#endif

/*901 难度中等 股票价格跨度*/
#if 0
/*
* 编写一个类，它收集某些股票的每日报价，并返回该股票当日价格的跨度
* 今天股价的跨度被定义为股票价格小于或等于今天价格的最大连续日数（包括今天）
*/
/*
* 思路：今日股价如果比昨天高的话，那跨度需要往前迭代，如果比昨天低，那跨度就只能是1。
* 因此只需要将局部最高的价格入栈
* 这题与739题的区别是，这一题事先没有一个完整的数组，因此需要同时保存价格和跨度
*/
#include <iostream>
#include <stack>

using namespace std;
class StockSpanner 
{
private:
    stack<pair<int,int>> stk;//prices and days

public:
    StockSpanner() 
    {

    }
    
    int next(int price) 
    {
        int day=1;
        while(!stk.empty() && price >= stk.top().first)
        {
            day += stk.top().second;
            stk.pop();
        }
        stk.push(pair(price,day));

        return day;
    }
};

#endif

/*1046 难度简单 最后一块石头的重量*/
#if 0
/*
* 有一堆石头，每一回合选出两块最重的石头，然后将它们一起粉碎。
*/
/*
* 思路：使用优先队列，判断前两个石头，然后将粉碎后的石头插入队列
*/
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int lastStoneWeight(vector<int>& stones) 
{
    priority_queue<int> pq;
    int first,second;
    for(int stone : stones)
    {
        pq.push(stone);
    }

    while(pq.size() > 1)
    {
        first = pq.top();
        pq.pop();
        second = pq.top();
        pq.pop();

        if(first > second)
        {
            pq.push(first - second);
        }
    }

    return pq.empty()? 0 : pq.top();
}

#endif

/* 692 难度中等 前K个高频单词*/
#if 0
/*
* 给定一个单词列表words和一个整数k，返回前k个出现次数最多的单词。
* 返回答案按照单词出现频率由高到低排序，相同频率按照字典排序
*/
/*
* 思路：将words加入哈希表，频率作为值，然后再将前k个键排序
* 键相等，则按照键的字典排序，键不相等，则按照值排序
*/
#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

unordered_map<string, int> wordsAndFrequency;
bool compare(const string &a,const string &b)
{
    if(wordsAndFrequency[a] == wordsAndFrequency[b])
    {
        return a < b;
    }
    else
    {
        return wordsAndFrequency[a] > wordsAndFrequency[b];
    }
}
vector<string> topKFrequent(vector<string>& words, int k) 
{
    for(auto &word :words)
    {
        wordsAndFrequency[word]++;
    }

    vector<string> sortString;
    for(auto & [key,value]:wordsAndFrequency)
    {
        sortString.push_back(key);
    }
    sort(sortString.begin(),sortString.end(),compare);

    sortString.erase(sortString.begin()+k,sortString.end());

    return sortString;
}

int main()
{

}

#endif

/*23 难度困难 合并k个升序链表*/
#if 0
/*
* 给你一个链表数组，每个链表都已经按升序排列，请将所有链表合并到升序链表中，返回合并后的链表
*/
/*
* 思路：将所有链表都往第一个链表上合并
*/
#include <iostream>
#include <vector>

using namespace std;
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* mergeTwoLists(ListNode* list1,ListNode* list2)
{
    ListNode *listHead = new ListNode();
    ListNode *prev = listHead;
    while((list1 != nullptr) && (list2 != nullptr))
    {
        if(list1->val < list2->val)
        {
            prev->next = list1;
            list1 = list1->next;
        }
        else
        {
            prev->next = list2;
            list2 = list2->next;
        }
        prev = prev->next;
    }

    prev->next = list1 == nullptr ? list2 : list1;

    return listHead->next;
}

ListNode* mergeKLists(vector<ListNode*>& lists) 
{
    ListNode *listHead = nullptr;

    for(int i = 0; i < lists.size(); ++i)
    {
        listHead = mergeTwoLists(listHead,lists[i]);
    }

    return listHead;
}
#endif

/*109 难度中等 有序链表转换二叉搜索树*/
#if 0
/*
* 给定一个单链表的头节点head，其中的元素按升序排序，将其转换成高度平衡的二叉搜索树
*/
/*
* 思路：先找出中值作为根节点，然后将链表分成两半
*/
#include <iostream>
using namespace std;
 struct ListNode 
 {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
ListNode* getMedianNode(ListNode* start,ListNode* end)
{
    ListNode* fast = start;
    ListNode* slow = start;
    //使用快慢节点来寻找中间节点
    while(fast != end && fast->next != end)
    {
        fast = fast->next;
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

TreeNode* buildTree(ListNode* start,ListNode* end)
{
    if(start == end)
    {
        return nullptr;
    }
    ListNode* mid = getMedianNode(start,end);
    TreeNode* root = new TreeNode(mid->val);

    root->left = buildTree(start,mid);
    root->right = buildTree(mid->next,end);

    return root;
}

TreeNode* sortedListToBST(ListNode* head) 
{
    return buildTree(head,nullptr);
}
int main()
{

}

#endif


/*890  难度中等 查找和替换模式*/
#if 0
/*
* 有一个单词列表words和一个模式pattern，想知道words中的哪些单词与模式匹配。
* 如果存在字母的排列p，使得模式中的每个字母x替换为p(x)后，就能得到所需单词，那么就是匹配的
*/
/*
* 思路：将模式作为key，单词作为value，如果键值对插入不成功则说明不匹配
*/
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <map>

using namespace std;

vector<string> findAndReplacePattern(vector<string>& words, string pattern)
{
    vector<string> newWords;

    for (auto word : words)
    {
        map<char, char> hashForward,hashReserve;
        pair<map<char, char>::iterator, bool> infoInsert;
        bool isForwardMatch = true, isReserveMatch = true;

        if (word.size() != pattern.size())
        {
            continue;
        }

        for (int i = 0; i < word.size(); ++i)
        {
            infoInsert = hashForward.insert(pair<char, char>(pattern[i], word[i]));

            if (infoInsert.second == false && word[i] != infoInsert.first->second)//插入失败
            {
                isForwardMatch = false;
                break;
            }

            infoInsert = hashReserve.insert(pair<char, char>(word[i], pattern[i])); 
            if (infoInsert.second == false && pattern[i] != infoInsert.first->second)//插入失败
            {
                isReserveMatch = false;
                break;
            }
        }


        if (isForwardMatch == true && isReserveMatch == true)
        {
            newWords.push_back(word);
        }
    }

    return newWords;
}

int main()
{

}
#endif

/*966 难度中等 元音拼写检查器*/
#if 0
/*
* 给定单词列表wordlist的情况下，将查询单词转换成正确的单词。
* 对于给定的查询单词query，会检查两类拼写错误：大小写错误、元音错误
*/
/*
* 思路：遍历queries，查询wordlist。先查询大小写问题，
*/
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

bool isSameAlphabet(char c1, char c2)
{
    if (c1 >= 'a' && c1 <= 'z')
    {
        if (c1 == c2 || c2 - c1 == 'A' - 'a')
        {
            return true;
        }
    }
    else
    {
        if (c1 == c2 || c1 - c2 == 'A' - 'a')
        {
            return true;
        }
    }
    return false;
}
bool isVowel(char c)
{
    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
        c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U' )
    {
        return true;
    }
    return false;
}
vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries)
{
    vector<string> answer;

    for (auto query : queries)
    {
        bool isMatch = false;
        //先匹配大小写
        for (auto word : wordlist)
        {
            if (word.size() != query.size())
            {
                continue;
            }
            for (int i = 0; i < word.size(); ++i)
            {
                isMatch = isSameAlphabet(word[i], query[i]);
                if (isMatch == false)
                {
                    break;
                }
            }
            if (isMatch == true)
            {
                answer.push_back(word);
                break;
            }
        }
        if(isMatch == false)
        {
            //再匹配元音
            for (auto word : wordlist)
            {
                if (word.size() != query.size())
                {
                    continue;
                }
                for (int i = 0; i < word.size(); ++i)
                {
                    isMatch = isVowel(word[i]) && isVowel(query[i]);
                    if (isMatch == true)
                    {
                        continue;
                    }
                    else
                    {
                        isMatch = isSameAlphabet(word[i], query[i]);
                        if (isMatch == false)
                        {
                            break;
                        }
                    }
                }
                if (isMatch == true)
                {
                    answer.push_back(word);
                    break;
                }
            }
        }
        if(isMatch == false)
        { 
            answer.push_back("");
        }
    }

    return answer;
}

int main()
{

}
#endif
/*966 难度中等 元音拼写检查器*/
#if 0
/*
* 思路：第一种情况：完全匹配：使用集合set来存放单词，用以检查单词是否存在
* 第二种情况：大小写不匹配：使用哈希表，该哈希表将单词从小写形式转换成大小写正确的形式
* 第三章情况：元音错误：使用哈希表，将单词从小写形式转换成元音正确的形式
* 将元音字符修改成通配符*，将字符串都改成小写
*/
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;

string stringToLower(const string & str)
{
    string lower(str);
    for(auto c : lower)
    {
        
    }
}

vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries)
{
    unordered_set<string> fullyMatch;
    unordered_map<string, string> capsMatch;
    unordered_map<string, string> vowelMatch;

    for(auto &word : wordlist)
    {
        fullyMatch.insert(word);

    }

}

int main()
{


}

#endif


/* 632 难度困难 最小区间 */
#if 0
/*
* 有k个非递减排列的整数，找到一个最小区间，使得k个列表中的每个列表至少有一个数包含其中
*/
/*
* 思路：使用最小堆
*/
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

 vector<int> smallestRange(vector<vector<int>>& nums) 
 {
    int rangeLeft = 0;
    int rangeRight = INT_MAX;
    int size = nums.size();
    vector<int> next(size);
    
    auto cmp = [&](const int& u, const int& v) 
    {
        return nums[u][next[u]] > nums[v][next[v]];
    };
    priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
    int minValue = 0, maxValue = INT_MIN;
    for (int i = 0; i < size; ++i) 
    {
        pq.emplace(i);
        maxValue = max(maxValue, nums[i][0]);
    }

    while (true) 
    {
        int row = pq.top();
        pq.pop();
        minValue = nums[row][next[row]];
        if (maxValue - minValue < rangeRight - rangeLeft) 
        {
            rangeLeft = minValue;
            rangeRight = maxValue;
        }
        if (next[row] == nums[row].size() - 1) 
        {
            break;
        }
        ++next[row];
        maxValue = max(maxValue, nums[row][next[row]]);
        pq.emplace(row);
    }

    return {rangeLeft, rangeRight};
}

#endif

/*61 难度中等 旋转链表*/
#if 0
/*
* 给定一个链表头节点head，旋转链表，将链表每个节点向右移动k个位置
*/
/*
* 思路：备份head，遍历到|k-n|%n个位置，第|k-n|%n个节点就是链表头。
*/
#include <iostream>
#include <algorithm>

using namespace std;
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* rotateRight(ListNode* head, int k)
{
    int rotateTimes=0;
    int listLenght=1;

    ListNode* lastNode = head;
    if(head == nullptr)
    {
        return nullptr;
    }

    while(head->next != nullptr)
    {
        listLenght++;
        head = head->next;
    }
    head->next = lastNode;

    rotateTimes = abs((k % listLenght) - listLenght);

    for(int i = 1; i < rotateTimes; ++i)
    {
        lastNode = lastNode->next;
    }
    head = lastNode->next;
    lastNode->next = nullptr;

    return head;
}
#endif

/*136 难度简单 只出现一次的数字*/
#if 0
/*
* 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。
* 找出那个只出现一次的元素
* 要求：算法应具有线性时间复杂度，不应该使用额外的空间
*/
/*
* 思路：使用集合或者哈希表来完成，但都不能达到时间复杂度和空间复杂度的要求
* 使用位运算可以完成。将数组中的全部元素进行异或即可。
*/
#include <iostream>
#include <set>
#include <vector>

using namespace std;

int singleNumber(vector<int>& nums) 
{
    set<int> table;

    for(auto n : nums)
    {
        pair<set<int>::iterator,bool> returnValue;
        returnValue = table.insert(n);
        if(returnValue.second == false)
        {
            table.erase(returnValue.first);
        }
    }
    return table.begin();
}

#endif

/*202 难度简单 快乐数*/
#if 0
/*
* 编写一个算法来判断n是不是快乐数
* 快乐数：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和
* 然后重复这个过程知道这个数字变成1，也可能是无限循环始终到不了1
* 如果这个过程结果为1，那么就是快乐数。
*/
/*
* 思路：先将一个整数分解，
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/*350 难度简单 两个数组的交集Ⅱ*/
#if 0
/*
* 给你两个整数数组nums1和nums2，请以数组的形式返回两个数组的交集
* 返回结果种每个元素出现的次数，应该与原来数组中出现的次数一致，如果不一致，择选最小的
*/
/*
* 思路：将第一个数组插入哈希表中，哈希表记录整数和整数出现的次数。
* 然后遍历第二个数组，如果哈希表中有这个数，则遍历下一个整数
* 如果哈希表中没有这个数，则说明是交集，将这个数写入返回的数组，并将哈希表中的次数减1
*/

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) 
{
    unordered_map<int,int> numsTimesMap;
    for(auto num : nums1)
    {
        //无论是否存在都要插入，因此使用下标插入
        numsTimesMap[num]++;
    }
    vector<int> intersection;

    for(auto num : nums2)
    {
        if(numsTimesMap.count(num) != 0)
        {
            intersection.push_back(num);
            numsTimesMap[num]--;

            if(numsTimesMap[num] == 0)
            {
                numsTimesMap.erase(num);
            }
        }
    }

    return intersection;
}

int main()
{

}

#endif

/*35 难度简单 搜索插入位置*/
#if 0
/*
* 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引
* 如果目标不在数组中，返回它将被插入的位置
*/
/*
* 思路：遍历数组，找到等于目标值的位置，如果没有则找到大于目标值的第一个数
*/

#include <iostream>
#include <vector

using namespace std;
int searchInsert(vector<int>& nums, int target) 
{
    int index = 0;
    for(int i = 0; i < nums.size(); ++i)
    {
        if(nums[i] >= target)
        {
            return i;
        }
        index = nums.size();
    }

    return index;
}

int main()
{

}

#endif

/*167 难度中等 输入有序数组*/
#if 0
/*
* 给定一个下标从1开始的数组numbers，已按照非递减顺序排列
* 从数组中找到满足相加之和等于目标数target的两个数。
* 以长度为2的数组的形式返回两个整数的下标
*/
/*
* 思路：双指针,start+end,如果大于target，则将end前移，如果小于target，则将start后移
*/

#include <iostream>
#include <vector>

using namespace std;

vector<int> twoSum(vector<int>& numbers, int target) 
{
    int start = 0,end = numbers.size() - 1;

    while(numbers[start] + numbers[end] != target)
    {
        if(numbers[start] + numbers[end]>target)
        {
            --end;
        }
        else
        {
            ++start;
        }
    }
    return (vector<int>{start+1,end+1});
}
int main()
{

}

#endif

/*148 难度中等 排序链表*/
#if 0
/*
* 给定链表头节点head，按照升序排列返回排序后的链表
*/
/*
* 思路：最适合链表的排序算法是归并排序。先找到链表中间节点，然后将其一分为二，
* 然后对两个子链表分别排序，最后将排序好的子链表合并。
*/

#include <iostream>

using namespace std;
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* sortList(ListNode* head)
{
    return sortList(head, nullptr);
}

ListNode* sortList(ListNode* head, ListNode* tail) 
{
    if (head == nullptr) 
    {
        return head;
    }
    if (head->next == tail) 
    {
        head->next = nullptr;
        return head;
    }
    ListNode* slow = head, *fast = head;
    while (fast != tail) 
    {
        slow = slow->next;
        fast = fast->next;
        if (fast != tail) 
        {
            fast = fast->next;
        }
    }
    ListNode* mid = slow;
    return merge(sortList(head, mid), sortList(mid, tail));
}

ListNode* merge(ListNode* head1, ListNode* head2) 
{
    ListNode* dummyHead = new ListNode(0);
    ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
    while (temp1 != nullptr && temp2 != nullptr) 
    {
        if (temp1->val <= temp2->val) 
        {
            temp->next = temp1;
            temp1 = temp1->next;
        } 
        else 
        {
            temp->next = temp2;
            temp2 = temp2->next;
        }
        temp = temp->next;
    }
    if (temp1 != nullptr) 
    {
        temp->next = temp1;
    } 
    else if (temp2 != nullptr) 
    {
        temp->next = temp2;
    }
    return dummyHead->next;
}

int main()
{

}

#endif

/*74 难度中等 搜索二维矩阵*/
#if 0
/*
* 编写一个高效的算法来判断mxn矩阵中，是否存在一个目标值。
* 矩阵每行中的整数从左到右升序排列，每行第一个整数大于前一行最后一个整数
*/
/*
* 思路：对矩阵第一列进行二分查找，找到最后一个不大于目标值的元素，然后再在那一行进行二分查找
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
bool searchMatrix(vector<vector<int>> matrix, int target) 
{
    auto row = upper_bound(matrix.begin(), matrix.end(), target, [](const int b, const vector<int> &a) {
        return b < a[0];
    });
    if (row == matrix.begin()) {
        return false;
    }
    --row;
    return binary_search(row->begin(), row->end(), target);
}

int main()
{

}

#endif

/*164 难度困难 最大间距*/
#if 0
/*
* 给定一个无序数组nums，返回数组排序后相邻元素之间最大差值。
*/
/*
* 思路：使用桶排序
*/

#include <iostream>
#include <vector>

using namespace std;
int maximumGap(vector<int>& nums) 
{
    int n = nums.size();
    int minVal = *min_element(nums.begin(), nums.end());
    int maxVal = *max_element(nums.begin(), nums.end());
    int d = max(1, (maxVal - minVal) / (n - 1));
    int bucketSize = (maxVal - minVal) / d + 1;

    if (n < 2) 
    {
        return 0;
    }

    vector<pair<int, int>> bucket(bucketSize, {-1, -1});
    for (int i = 0; i < n; i++) {
        int idx = (nums[i] - minVal) / d;
        if (bucket[idx].first == -1) 
        {
            bucket[idx].first = bucket[idx].second = nums[i];
        } 
        else 
        {
            bucket[idx].first = min(bucket[idx].first, nums[i]);
            bucket[idx].second = max(bucket[idx].second, nums[i]);
        }
    }

    int ret = 0;
    int prev = -1;
    for (int i = 0; i < bucketSize; i++) 
    {
        if (bucket[i].first == -1) continue;
        if (prev != -1) 
        {
            ret = max(ret, bucket[i].first - bucket[prev].second);
        }
        prev = i;
    }
    return ret;
}

int main()
{

}

#endif

/*27 难度简单 移除元素*/
#if 0
/*
* 给定一个数组nums和一个值val，你需要原地移除所有数值等于valu的元素，并返回移除后数组的心长度。
* 不适用额外数组空间
*/
/*
* 思路：遍历nums，记录等于val的个数n，如果不等于val，则前移n位，如果等于val，则n+1
*/

#include <iostream>

using namespace std;
int removeElement(vector<int>& nums, int val) 
{
    int n = 0;

    for(int i = 0; i < nums.size(); ++i)
    {
        if (nums[i] == val)
        {
            n += 1;
        }
        else
        {
            nums[i-n] = nums[i];
        }
    }
    return nums.size() - n;
}
int main()
{

}

#endif

/*3 难度中等 无重复字符的最长子串*/
#if 0
/*
* 给定一个字符串s，找出不含重复字符的最长字串的长度。
*/
/*
* 思路1：遍历字符串，用指针start指向不重复子串的首部，另一个指针end向下遍历
* 当找到一个重复字符时，记录当前不重复子串最大长度，然后让start指向前面一个重复字符的下一个
* 思路2：以start指针为开头，寻找最长的不重复的子串，并以end结尾，记录当前子串长度
* 将字符插入到哈希表中，然后将start右移，移除哈希表中start指向的元素，end也继续右移
* 思路点评：本质上两种方法都是使用双指针，思路1中的start在移动的时候更为精确，减少了迭代次数
* 但查重的时候重新构造了一个字符串，并使用find查重，查重效率没有哈希表高
*/

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

int lengthOfLongestSubstring(string s)
{
    int start = 0,end = 0;
    int maxLength = 0;
    set<char> hashMap;

    while (end != s.size())
    {
        end++;
        
        string* str = new string(s, start, end - start);
        size_t it = str->find(s[end]);//it指向的是新字符串的索引

        maxLength = max(end - start, maxLength);

        if (it != string::npos)
        {
            start = start + it + 1;//在s中的索引还需要加上str的初始位置start
        }
    }

    return maxLength;
}

int main()
{

}

#endif

/*209 难度中等 长度最小的子串*/
#if 0
/*
* 给定一个含有n个正整数的数组和一个正整数target。
* 找出数组中满足其和大于等于target的长度最小的连续子数组[nums]，并返回其长度，不存在则返回0。
*/
/*
* 思路：利用双指针，如果[start,end]<target，则移动end
* 如果[start,end]>=target，则记录当前长度，并移动start
* 优化：每次都计算[start,end]的累加和导致时间复杂度过高
* 通过标记是end移动还是start移动，就可以利用上一次的累加和来调整这一次的累加和
*/

#include <iostream>
#include <algorithm>

using namespace std;
int minSubArrayLen(int target, vector<int>& nums) 
{
    int start = 0,end = 0;
    int length = INT_MAX;
    int sum = 0;
    bool isEndMove = true;
    
    while(end != nums.size())
    {
        if(isEndMove == true)
        {
            sum += nums[end];
        }
        else
        {
            sum -= nums[start-1];
        }

        if(sum < target)
        {
            isEndMove = true;
            ++end;
        }
        else
        {
            isEndMove = false;
            length = min(length,end - start + 1);
            ++start;
        }
    }

    if(nums.size() == 0 || start == 0)
    {
        return 0;
    }

    return length;
}

int main()
{

}

#endif

/*845 难度中等 数组中的最长山脉*/
#if 0
/*
* 把符合下列属性的数组arr成为山脉数组
* 1、arr.length>=3
* 2、存在下标i，满足i左边的数递增，i右边的数递减
* 给定一个数组arr，返回最长山脉数组的长度，不存在则返回0
*/
/*
* 思路：双指针，start标记开头，end向后遍历。用状态机的方式来实现，首先设置当前状态为stable。
* 如果当前处于stable状态，若遇到相等或者递减，则移动start，若遇到递增，则改为increase状态
* 如果当前处于increase状态，若遇到递减，则修改为递减状态；若遇到相等，则修改为stable状态，并移动start。若递增，则继续。
* 如果当前处于decrease状态，若遇到相等、递增、结束了，则找到山脉，记录最长山脉。若递减，则继续。
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef enum increaseState
{
    increase,
    decrease,
    stable
};
int longestMountain(vector<int>& arr) 
{
    enum increaseState lastState = stable;
    int start = 0,end = 0;
    int maxLength = 0;

    for(end = 1; end < arr.size(); ++end)
    {
        switch (lastState)
        {
        case stable:
            if(arr[end] > arr[end-1])
            {
                lastState = increase;
            }
            else
            {
                start = end;
            }
            break;
        case increase:
            if(arr[end] < arr[end-1])
            {
                lastState = decrease;
            }
            else if(arr[end] = arr[end-1])
            {
                lastState = stable;
                start = end;
            }
            break;
        case decrease:
            if(arr[end] >= arr[end-1])
            {
                lastState = stable;
                maxLength = max(maxLength,end-start);
                start = end;
            }
            else if(arr[end] < arr[end-1] && end == arr.size() - 1)
            {
                maxLength = max(maxLength,end-start + 1);                
            }
            break;
        
        default:
            break;
        }
    }
    return maxLength;
}

int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif

/**/
#if 0
/*
* 
*/
/*
* 思路：
*/

#include <iostream>

using namespace std;


int main()
{

}

#endif
